Inexact Regularized Proximal Newton Method: Provable Convergence Guarantees for Non-Smooth Convex Minimization without Strong Convexity

摘要

We propose a second-order method, the inexact regularized proximal Newton(IRPN) method, to minimize a sum of smooth and non-smooth convex functions. Weprove that the IRPN method converges globally to the set of optimal solutionsand the asymptotic rate of convergence is superlinear, even when the objectivefunction is not strongly convex. Key to our analysis is a novel usage of acertain error bound condition. We compare two empirically efficientalgorithms---the newGLMNET and adaptively restarted FISTA---with our proposedIRPN by applying them to the $\ell_1$-regularized logistic regression problem.Experiment results show the superiority of our proposed algorithm.